package backtrackStudy;

import java.util.LinkedList;
import java.util.List;

public class Combine {

    //存放结果
    private static LinkedList<LinkedList<Integer>> res = new LinkedList<>();

    /**
     * LeetCode T77 组合
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     *
     * 组合问题——遍历层级确定
     * @param args
     */
    public static void main(String[] args) {

    }

    public static LinkedList<LinkedList<Integer>> combine(int n, int k){
        LinkedList<Integer> trace = new LinkedList<>();
        backtrace(n, k, 0, trace);
        return res;
    }

    //确定参数
    public static void backtrace(int n, int k, int beginIndex, LinkedList<Integer> trace){
        //定义出口，确定终止条件
        if (trace.size() == k){
            res.add(new LinkedList<>(trace));
            return;
        }

        //可以进行剪枝优化
        for (int i = beginIndex; i < n + trace.size() - k; i++){
            //记录路径
            trace.addLast(i + 1);
            //进行递归
            backtrace(n, k,i + 1, trace);
            //消除记录
            trace.removeLast();
        }
    }
}
